import random


def max_subarray_num(nums):
    n = len(nums)
    if n == 0:
        return 0

    acc = [0]
    for x in nums:
        acc.append(acc[-1] + x)
    all_sum = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(i+1):
            all_sum[i][j] = acc[i+1] - acc[j]
    # 截至目前，k这个区间和最多出现a次，出现a次最少消耗b个元素
    all_sum_values = set(all_sum[i][j] for i in range(n) for j in range(i+1))
    stat = {k: [0, 0] for k in all_sum_values}
    for i, x in enumerate(nums):
        for j in range(i + 1):
            a, b = stat[all_sum[i][j]]
            if j >= b:
                a += 1
                b = i + 1
                stat[all_sum[i][j]] = [a, b]
    result = max(a for a, b in stat.values())
    return result


# nums = [8, 8, 9, 1, 9, 6, 3, 9, 1, 0]
# print(max_subarray_num(nums))
#
# nums = [-1, 0, 4, -3, 6, 5, -6, 5, -7, -3]
# print(max_subarray_num(nums))

# nums = list(range(1000))
# print(max_subarray_num(nums))

nums = random.choices(range(-5000, 5000), k=1000)
print(max_subarray_num(nums))




